The advent of powerful computers and large storage disks, such as CD-ROMs, in recent years, has brought with it a surge in production and use of sophisticated multimedia graphics applications. In order to transmit such applications over the Internet, new data types have been defined, including three-dimensional triangle mesh data objects. Files used with the VRML97 graphics standard include such types of three dimensional objects. VRML97 files represent graphic objects using ASCII-based data and have large amounts of redundancy.
Generally, a three-dimensional triangle mesh object comprises a plurality of triangles identified by their vertices. The triangle mesh is represented by a list of triangles, in which for each triangle the coordinates of its three vertices are indicated. The information in the list includes the coordinates of the vertices, and indication of which vertices belong to each triangle. The information regarding the coordinates is referred to as the geometry of the object, while information pertaining to which vertices belong to each triangle is referred to as the topology or connectivity of the object.
A triangle mesh representation of a complex, three-dimensional object generally includes a large volume of data. However, the communication lines through which such data may be transferred over the Internet or other networks typically have a limited average rate of data transfer, commonly referred to as bandwidth. Therefore, it is important to compress data objects as best possible before transfer. The better the compression method which is used, the more data can be transferred in a given amount of time.
A scheme for compression of VRML97 graphics files has been suggested by IBM (http://www.research.ibm.com/vrml/binary/specification). This scheme involves tokenizing the ASCII content of the files into binary form and compressing the data using a polygonal mesh compression algorithm due to Taubin, et al. (G. Taubin and J. Rossignac, "Geometric compression through topological surgery," Research Report RC-20340, IBM Research Division, 1996). Taubin's algorithm compresses the geometry data by quantizing the coordinates of the mesh to 8, 10 or 12 bits and then using a linear prediction algorithm. The integer prediction errors are encoded by an entropy rate algorithm. In average cases, Taubin achieves a compression rate of about 13 bits per vertex for the geometry data.
However, better compression schemes are sought in order to allow more rapid transfer of three dimensional data objects.